package algorithm.linkedlist;

import algorithm.model.ListNode;

/**
 * leetcode : https://leetcode.com/problems/swap-nodes-in-pairs/description/
 * Diffculty: Medium
 *
 * 一个单向列表，将节点数据两两交换
 * 例如:1-2-3-4-5-6，则交换后的结果为 2-1-4-3-6-5
 *
 * @Author Antony
 * @Since 2018/6/26 17:44
 */
public class SwapNodesInPairs {


    public static void main(String[] args) {
        ListNode initNode = ListNode.initDate(1,7);
        System.out.println(initNode.nodeString());
//        ListNode swapNode = swapPairs(initNode);
//        System.out.println(swapNode.convertToString());

        ListNode dummyNode = dummySwapPairs(initNode);
        System.out.println(dummyNode.nodeString());

    }

    /**
     * (leetcode beats 100%)
     * 建立一个单节点当做栈，
     * 如果节点为null，则赋值并且next后移。
     * 如果节点不为null，则取得当前节点后，把其取出来再追加到后面。
     *
     * @param head
     * @return
     */
    public static ListNode swapPairs(ListNode head) {
        ListNode sentinel = null;
        ListNode currNode = new ListNode(-1);
        ListNode first = currNode;

        while(head != null){
            if(sentinel == null){
                sentinel = head;
                head = head.next;
                sentinel.next = null;
            }else{
                ListNode headNode = head;
                head = head.next;
                currNode = currNode.next = headNode;
                currNode = currNode.next = sentinel;
                sentinel = null;
            }
        }
        if(sentinel != null){
            currNode.next = sentinel;
        }

        return first.next;
    }

    /**
     * 在LeetCode上看到的解法
     * https://leetcode.com/problems/swap-nodes-in-pairs/discuss/11046/My-simple-JAVA-solution-for-share
     * @param head
     * @return
     */
    public static ListNode dummySwapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode current = dummy;
        while (current.next != null && current.next.next != null) {
            ListNode first = current.next;
            ListNode second = current.next.next;
            first.next = second.next;
            current.next = second;
            current.next.next = first;
            current = current.next.next;
        }
        return dummy.next;
    }


}
